package com.itheima.d4_collection_set;

/**
 * PPT：day06，视频第140集
 *
 * 目标：了解一下哈希值。
 * 注意：在正式了解HashSet集合的底层原理前，我们需要先搞清楚一个前置知识：哈希值
 * 哈希值:
 * 就是一个int类型的数值，Java中每个对象都有一个哈希值。
 * Java中的所有对象，都可以调用Obejct类提供的hashCode方法，返回该对象自己的哈希值。
 *public int hashCode()：返回对象的哈希值。
 * 同一个对象多次调用hashCode()方法返回的哈希值是相同的。
 * 不同的对象，它们的哈希值一般不相同，但也有可能会相同(哈希碰撞)。
 */

/*
HashSet集合的底层原理:
基于哈希表实现。
哈希表是一种增删改查数据性能都较好的结构。
    分析：寻找某一个数据的时候，只需要计算出数据的哈希值然后对数组求余，得到数组的索引值，就可以很方便的用索引值去操作数组

JDK8之前HashSet集合的底层原理，基于哈希表：数组+链表
    1.创建一个默认长度16的数组，默认加载因子为0.75，数组名table
    2.使用元素的哈希值对数组的长度求余计算出应存入的位置
    3.判断当前位置是否为null，如果是null直接存入
    4.如果不为null，表示有元素，则调用equals方法比较属性值: 如果一样，则不存，如果不一样，则存入数组。
      扩容：当数组存满到16*0.75=12时，就自动扩容，每次扩容原先的两倍
    5.JDK 8之前，新元素存入数组，占老元素位置，老元素挂下面
    6.JDK 8开始之后，新元素直接挂在老元素下面

(以上就是hashSet无序！不重复！无索引！的原因)
    无序：每一个元素存入hashSet集合都需要计算出元素的哈希值，然后对数组长度求余计算出在数组中的位置，
         所以在hashSet集合中读出来的数据肯定是和添加元素的顺序是不同的，但却是固定的顺序而不会每次输出集合都是随机的顺序
    不重复：每一个元素计算出哈希值，然后假设计算出来的数组索引值的位置是有元素不为空的，（不一定是同一个对象，也有可能是其他元素计算出了相同的索引），
           那就会再进行equals判断，equals结果是true那就去掉重复的数据，不一样就会用链表的形式存入数组

如果数组快占满了还是要添加大量元素，就有可能导致数组某个索引处存放的链表会过长，而链表查询性能较低，就会导致查询性能低
    扩容：加载因子0.75是指16的0.75=12，一但占满了数组的12个位置，就会进行扩容
但是假设扩容后，还是有很多元素计算出来的数组索引值都是相同的，都要占据同一个位置，那么还是会导致链表过长
    JDK8开始HashSet集合的底层原理，基于哈希表：数组 + 链表 + 红黑树
        JDK8开始，当链表长度超过8，且数组长度>=64时，自动将链表转成红黑树
 */

/*
二叉树中，任意节点的度<=2
度：每一个节点的子节点数量
树高：树的总层数
根节点：最顶层的节点
普通的二叉树

进化：二叉查找树（二叉排序树）:
    小的存左边，大的存右边，一样的不存
二叉查找树存在的问题：
    当数据已经是排好序的，极端情况下例如1,2,3，4会导致树的结构和单链表一样（瘸子现象），查询的性能也和单链表一样，查询速度变慢！

再次进化平衡二叉树：
    在满足查找二叉树的大小规则下，让树尽可能矮小，以此提高查数据的性能。

终极进化：红黑树，就是可以自平衡的二叉树
    红黑树是一种增删改查数据性能相对都较好的结构。
 */
public class SetTest2 {
    public static void main(String[] args) {
        System.out.println("以下都建立在student是没有在setTest3案例重写过几个方法的前提下： ");
        Student s1 = new Student("蜘蛛精",25, 169.5);
        Student s2 = new Student("紫霞",22, 166.5);
        Student s3 = new Student("紫霞",22, 166.5);
        System.out.println(s1.hashCode());
        System.out.println(s1);             //com.itheima.d4_collection_set.Student@776ec8df
        System.out.println("输出几次s1，哈希值都一样2003749087: "+s1.hashCode());
        System.out.println(s2.hashCode());
        System.out.println(s2);             //com.itheima.d4_collection_set.Student@58372a00
        System.out.println("输出几次s2，哈希值都一样1480010240: "+s2.hashCode());
        System.out.println("s2和s3是内容相同的对象，s3哈希值:81628611-- "+s3.hashCode());
        System.out.println(s3);             //com.itheima.d4_collection_set.Student@4dd8dc3
        System.out.println("s2和s3是内容相同的对象，但是两个对象在堆内存的地址值不同，得到的哈希值不同，hashset不能去重");

        System.out.println("---------------------------");

        //哈希值相同的例子：
        // String类的hashCode()方法把字符值代入特定公式计算哈希值，知道公式就能轻易设计出哈希碰撞
        String str1 = new String("abc");
        String str2 = new String("acD");
        System.out.println(str1.hashCode());
        System.out.println(str2.hashCode());
        String str3 = ("abc");
        System.out.println(str3.hashCode());
    }
}
